package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/find-missing-and-repeated-values/'>找出缺失和重复的数字(Find Missing and Repeated Values)</a>
 * <p>给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n^2] 范围内。除了 a 出现 两次，b 缺失 之外，每个整数都 恰好出现一次 。</p>
 * <p>任务是找出重复的数字a 和缺失的数字 b 。</p>
 * <p>返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：grid = [[1,3],[2,2]]
 *      输出：[2,4]
 *      解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。
 *
 * 示例 2：
 *      输入：grid = [[9,1,7],[8,9,2],[3,4,6]]
 *      输出：[9,5]
 *      解释：数字 9 重复，数字 5 缺失，所以答案是 [9,5] 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>2 <= n == grid.length == grid[i].length <= 50</li>
 *      <li>1 <= grid[i][j] <= n * n</li>
 *      <li>对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。</li>
 *      <li>对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。</li>
 *      <li>除上述的两个之外，对于所有满足1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x 。</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/23 9:21
 */
public class LC2965FindMissingAndRepeatedValues_S {

    static class Solution {
        public int[] findMissingAndRepeatedValues(int[][] grid) {
            int[] cnt = new int[grid.length * grid.length + 1];
            for (int[] rows : grid) {
                for (int j = 0; j < grid[0].length; j++) {
                    ++cnt[rows[j]];
                }
            }
            int[] resArr = new int[2];
            for (int i = 1; i < cnt.length; i++) {
                if (cnt[i] == 2) {
                    resArr[0] = i;
                }
                if (cnt[i] == 0) {
                    resArr[1] = i;
                }
            }
            return resArr;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.findMissingAndRepeatedValues(new int[][]{{1, 3}, {2, 2}}));
        Printer.printArrayInt(solution.findMissingAndRepeatedValues(new int[][]{{9, 1, 7}, {8, 9, 2}, {3, 4, 6}}));
    }
}
